home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / c-runtime / dispatch / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-18  |  13.7 KB  |  363 lines
  1. /* -*-c-*- */
  2.  
  3. /* Copyright (C) 1989, 1992 Free Software Foundation, Inc.
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 2, or (at your option)
  10. any later version.
  11.  
  12. GNU CC is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU CC; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. /* As a special exception, if you link this library with files
  22.    compiled with GCC to produce an executable, this does not cause
  23.    the resulting executable to be covered by the GNU General Public License.
  24.    This exception does not however invalidate any other reasons why
  25.    the executable file might be covered by the GNU General Public License.  */
  26.  
  27. /* 
  28.   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/dispatch/RCS/hash.c,v 0.13 1992/08/18 04:46:58 dglattin Exp $
  29.   $Author: dglattin $
  30.   $Date: 1992/08/18 04:46:58 $
  31.   $Log: hash.c,v $
  32.  * Revision 0.13  1992/08/18  04:46:58  dglattin
  33.  * Saving a working version before release.
  34.  *
  35.  * Revision 0.12  1992/04/13  11:43:08  dennisg
  36.  * Check in after array version of run-time works.
  37.  * Expect more changes as hash version and other changes are made.
  38.  *
  39.  * Revision 0.11  1992/01/03  02:55:03  dennisg
  40.  * modified to handle new initialization scheme.
  41.  * fixed code structure.
  42.  *
  43.  * Revision 0.10  1991/12/10  12:05:28  dennisg
  44.  * Cleaned up file format for a distribution.
  45.  *
  46.  * Revision 0.9  1991/12/03  02:01:23  dennisg
  47.  * fixed assert macro.
  48.  * added memory allocation adjustment macro for hash size allocation.
  49.  *
  50.  * Revision 0.8  1991/11/24  01:20:02  dennisg
  51.  * changed shorts back to ints.
  52.  * the efficiency gained didn't out weight the grossness of the code.
  53.  *
  54.  * Revision 0.7  1991/11/23  22:18:29  dennisg
  55.  * deleted hashIndex() and moved it to hash-inline.h
  56.  * converted hash_value_for_key () to a inline and moved it to hash-inline.h.
  57.  *
  58.  * Revision 0.6  1991/11/21  22:27:06  dennisg
  59.  * changed hash value calculation.
  60.  * func name changed from hashValue () to hashIndex().  the
  61.  * func really calculated a index anyway.
  62.  * changed hash func impl.  essentially it was calculating a hash value
  63.  * from a hash value.  this is a implementation thing.
  64.  *
  65.  * Revision 0.5  1991/11/20  23:29:20  dennisg
  66.  * converted hashIndex() to a inline.
  67.  *
  68.  * Revision 0.4  1991/11/19  12:34:41  dennisg
  69.  * bug in hash_delete ().  It was using void* to obtain nodes to
  70.  * pass to hash_remove ().  The value passed to hash_removed () is a
  71.  * entry from the node structure rather than the node itself.  Using
  72.  * void* removed compiler checking.
  73.  * Modified to implement cache expansion.
  74.  *
  75.  * Revision 0.3  1991/11/07  23:23:40  dennisg
  76.  * implemented hash table expansion as suggested by rms.
  77.  *
  78.  * Revision 0.2  1991/11/07  22:30:54  dennisg
  79.  * added copyleft
  80.  *
  81.  * Revision 0.1  1991/10/24  00:45:39  dennisg
  82.  * Initial check in.  Preliminary development stage.
  83.  *
  84. */
  85.  
  86.  
  87. #include  <hash.h>
  88. #include  <objc.h>
  89. #include  <objcP.h>
  90. #include  <objc-protoP.h>
  91.  
  92. #include  <assert.h>
  93. #include  <math.h>
  94. #include  <stdio.h>
  95. #include  <stdlib.h>
  96.  
  97.  
  98.                                                 /* These two macros determine
  99.                                                   when a hash table is full and
  100.                                                   by how much it should be 
  101.                                                   expanded respectively.
  102.                                                   
  103.                                                   These equations are 
  104.                                                   percentages. */
  105. #define FULLNESS(cache) \
  106.    ((((cache)->sizeOfHash * 75  ) / 100) <= (cache)->entriesInHash)
  107. #define EXPANSION(cache) \
  108.   ((cache)->sizeOfHash * 2 )
  109.  
  110. Cache_t 
  111. hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc) {
  112.  
  113.   Cache_t retCache;
  114.   
  115.  
  116.                                                                                                 /* Pass me a value greater
  117.                                                                                                     than 0 and a power of 2. */
  118.   assert(sizeOfHash);
  119.     assert( !(sizeOfHash & (sizeOfHash - 1)));
  120.   
  121.                                                 /* Allocate the cache 
  122.                                                   structure.  calloc () insures
  123.                                                   its initialization for
  124.                                                   default values. */
  125.   retCache = calloc (1, sizeof (Cache));
  126.   assert(retCache);
  127.   
  128.                                                 /* Allocate the array of 
  129.                                                   buckets for the cache.  
  130.                                                   calloc() initializes all of 
  131.                                                   the pointers to NULL. */
  132.   retCache->theNodeTable = calloc (sizeOfHash, sizeof (CacheNode_t));
  133.   assert(retCache->theNodeTable);
  134.   
  135.   retCache->sizeOfHash  = sizeOfHash;
  136.  
  137.                                                                                                 /* This should work for all
  138.                                                                                                     processor architectures? */
  139.     retCache->mask = ( sizeOfHash - 1 );
  140.     
  141.                                                                                                 /* Store the hashing function
  142.                                                                                                     so that codes can be 
  143.                                                                                                     computed. */
  144.     retCache->hashFunc = aHashFunc;
  145.  
  146.                                                                                                 /* Store the function that
  147.                                                                                                     compares hash keys to 
  148.                                                                                                     determine if they are 
  149.                                                                                                     equal. */
  150.     retCache->compareFunc = aCompareFunc;
  151.  
  152.   return retCache;
  153. }
  154.  
  155.  
  156. void 
  157. hash_delete (Cache_t theCache) {
  158.  
  159.   CacheNode_t aNode;
  160.   
  161.  
  162.                                                /* Purge all key/value pairs 
  163.                                                   from the table. */
  164.   while (aNode = hash_next (theCache, NULL))
  165.     hash_remove (theCache, aNode->theKey);
  166.  
  167.                                                 /* Release the array of nodes 
  168.                                                   and the cache itself. */
  169.   free (theCache->theNodeTable);
  170.   free (theCache);
  171. }
  172.  
  173.  
  174. void 
  175. hash_add (Cache_t* theCache, void* aKey, void* aValue) {
  176.  
  177.   u_int       indx = (* (*theCache)->hashFunc)(*theCache, aKey);
  178.   CacheNode_t aCacheNode = calloc (1, sizeof (CacheNode));
  179.  
  180.  
  181.   assert(aCacheNode);
  182.   
  183.                                                 /* Initialize the new node. */
  184.   aCacheNode->theKey    = aKey;
  185.   aCacheNode->theValue  = aValue;
  186.   aCacheNode->nextNode  = (* (*theCache)->theNodeTable)[ indx ];
  187.   
  188.                                                 /* Debugging.
  189.                                                 
  190.                                                   Check the list for another 
  191.                                                   key. */
  192. #ifdef DEBUG
  193.     { CacheNode_t checkHashNode = (* (*theCache)->theNodeTable)[ indx ];
  194.     
  195.       while (checkHashNode) {
  196.     
  197.         assert(checkHashNode->theKey != aKey);
  198.         checkHashNode = checkHashNode->nextNode;
  199.       }
  200.     }
  201. #endif
  202.  
  203.                                                 /* Install the node as the
  204.                                                   first element on the list. */
  205.   (* (*theCache)->theNodeTable)[ indx ] = aCacheNode;
  206.  
  207.                                                 /* Bump the number of entries
  208.                                                   in the cache. */
  209.   ++ (*theCache)->entriesInHash;
  210.   
  211.                                                 /* Check the hash table's
  212.                                                   fullness.   We're going
  213.                                                   to expand if it is above
  214.                                                   the fullness level. */
  215.   if (FULLNESS (*theCache)) {
  216.                                                 /* The hash table has reached
  217.                                                   its fullness level.  Time to
  218.                                                   expand it. 
  219.                                                   
  220.                                                   I'm using a slow method 
  221.                                                   here but is built on other
  222.                                                   primitive functions thereby
  223.                                                   increasing its 
  224.                                                   correctness. */
  225.     CacheNode_t aNode = NULL;
  226.     Cache_t     newCache = hash_new (EXPANSION (*theCache), 
  227.                                                                          (*theCache)->hashFunc, 
  228.                                                                          (*theCache)->compareFunc);
  229.  
  230.     DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n",
  231.       *theCache, (*theCache)->sizeOfHash, newCache->sizeOfHash);
  232.       
  233.                                                 /* Copy the nodes from the
  234.                                                   first hash table to the
  235.                                                   new one. */
  236.     while (aNode = hash_next (*theCache, aNode))
  237.       hash_add (&newCache, aNode->theKey, aNode->theValue);
  238.  
  239.                                                 /* Trash the old cache. */
  240.     hash_delete (*theCache);
  241.     
  242.                                                 /* Return a pointer to the new
  243.                                                   hash table. */
  244.     *theCache = newCache;
  245.   }
  246. }
  247.  
  248.  
  249. void 
  250. hash_remove (Cache_t theCache, void* aKey) {
  251.  
  252.   u_int       indx = (*theCache->hashFunc)(theCache, aKey);
  253.   CacheNode_t aCacheNode = (*theCache->theNodeTable)[ indx ];
  254.   
  255.   
  256.                                                 /* We assume there is an entry 
  257.                                                   in the table.  Error if it 
  258.                                                   is not. */
  259.   assert(aCacheNode);
  260.   
  261.                                                 /* Special case.  First element 
  262.                                                   is the key/value pair to be 
  263.                                                   removed. */
  264.   if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
  265.     (*theCache->theNodeTable)[ indx ] = aCacheNode->nextNode;
  266.     free (aCacheNode);
  267.   } else {
  268.                                                 /* Otherwise, find the hash 
  269.                                                   entry. */
  270.     CacheNode_t prevHashNode = aCacheNode;
  271.     BOOL        removed = NO;
  272.     
  273.     do {
  274.     
  275.       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
  276.         prevHashNode->nextNode = aCacheNode->nextNode, removed = YES;
  277.         free (aCacheNode);
  278.       } else
  279.         prevHashNode = aCacheNode, aCacheNode = aCacheNode->nextNode;
  280.     } while (!removed && aCacheNode);
  281.     assert(removed);
  282.   }
  283.   
  284.                                                 /* Decrement the number of
  285.                                                   entries in the hash table. */
  286.   --theCache->entriesInHash;
  287. }
  288.  
  289.  
  290. CacheNode_t 
  291. hash_next (Cache_t theCache, CacheNode_t aCacheNode) {
  292.  
  293.   CacheNode_t theCacheNode = aCacheNode;
  294.   
  295.   
  296.                                                 /* If the scan is being started
  297.                                                   then reset the last node 
  298.                                                   visitied pointer and bucket 
  299.                                                   index. */
  300.   if (!theCacheNode)
  301.     theCache->lastBucket  = 0;
  302.   
  303.                                                 /* If there is a node visited
  304.                                                   last then check for another 
  305.                                                   entry in the same bucket; 
  306.                                                   Otherwise step to the next 
  307.                                                   bucket. */
  308.   if (theCacheNode)
  309.     if (theCacheNode->nextNode)
  310.                                                 /* There is a node which 
  311.                                                   follows the last node 
  312.                                                   returned.  Step to that node 
  313.                                                   and retun it. */
  314.       return theCacheNode->nextNode;
  315.     else
  316.       ++theCache->lastBucket;
  317.  
  318.                                                 /* If the list isn't exhausted 
  319.                                                   then search the buckets for 
  320.                                                   other nodes. */
  321.   if (theCache->lastBucket < theCache->sizeOfHash) {
  322.                                                 /*  Scan the remainder of the 
  323.                                                   buckets looking for an entry
  324.                                                   at the head of the list.  
  325.                                                   Return the first item 
  326.                                                   found. */
  327.     while (theCache->lastBucket < theCache->sizeOfHash)
  328.       if ((*theCache->theNodeTable)[ theCache->lastBucket ])
  329.         return (*theCache->theNodeTable)[ theCache->lastBucket ];
  330.       else
  331.         ++theCache->lastBucket;
  332.   
  333.                                                 /* No further nodes were found
  334.                                                   in the hash table. */
  335.     return NULL;
  336.   } else
  337.     return NULL;
  338. }
  339.  
  340.  
  341.                                                 /* Given key, return its 
  342.                                                   value.  Return NULL if the
  343.                                                   key/value pair isn't in
  344.                                                   the hash. */
  345. void* 
  346. hash_value_for_key (Cache_t theCache, void* aKey) {
  347.  
  348.   CacheNode_t aCacheNode = 
  349.               (*theCache->theNodeTable)[(*theCache->hashFunc)(theCache, aKey)];
  350.   void*       retVal = NULL;
  351.   
  352.  
  353.   if (aCacheNode)
  354.     do {
  355.       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey))
  356.         retVal = aCacheNode->theValue;
  357.       else
  358.         aCacheNode = aCacheNode->nextNode;
  359.     } while (!retVal && aCacheNode);
  360.   
  361.   return retVal;
  362. }
  363.